import java.util.*;

public class Code_49 {
    /**
     * 这道题本质上把“相同”但乱序的字符串放在一起，所以要简化问题，先把每个字符串排序再比较。
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        // Map 来存储每个字谜组，key 为排序后的字符串，value 为该字谜组的所有字符串
        Map<String, List<String>> map = new HashMap<>();

        // 遍历字符串数组
        for (String str : strs) {
            // 将字符串排序并作为 key
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);

            // 如果 map 中没有这个键，先初始化一个空列表
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }

            // 将当前字符串添加到对应字谜组的列表中
            map.get(sortedStr).add(str);
        }

        // 将 map 中的所有字谜组转换为 List<List<String>> 返回
        return new ArrayList<>(map.values());
    }
}
